Since a storage medium is subject to various types of noise, distortion and interference, various errors can occur at the output of the storage medium. The current trend is to store greater amounts of digital data in smaller areas on the storage medium. This trend increases the probability of errors. To correct the errors, error correction coding is used. One class of such error correction codes is the well-known Reed Solomon (RS) codes.
The Reed Solomon (RS) encoding technique appends to each block of k user data symbols 2t redundancy symbols to create a codeword (where t represents the designed symbol error correcting capacity of the code). There are k+2t symbols in a RS codeword. The RS code views the n-bit symbols as elements of a Galois Field (GF(2.sup.n)). A Galois field is a finite field, the elements of which may be represented as polynomials in a, where a is a root of an irreducible polynomial of degree n. The RS codeword consists of a block of n-bit symbols. Typically, n=8 and the 8-bit symbols are referred to as bytes. Constructing the Galois field GF(2.sup.n) requires a defining polynomial f(x) of degree n. In addition, a primitive element .beta. is chosen so that every nonzero element of GF(2.sup.n) is a power of .beta.. The element .beta. is not necessarily a root of f(x).
A RS codeword C is viewed as a polynomial C(x) and the redundancy symbols are chosen so that the roots of C(x) include the roots of a generator polynomial G(x) whose roots are 2t consecutive powers of .beta.. The k user data symbols are viewed as the high order coefficients of a degree k+2t-1 polynomial, and the redundancy symbols are the coefficients of the remainder when this polynomial is divided by G(x).
The process of corrupting the original code block C(x) with errors can be viewed as adding an error polynomial E(x) to C(x). The resultant corrupted polynomial is known as the received polynomial R(x), where R(x)=C(x)+E(x).
The v non-zero terms of the error polynomial contain the necessary information to completely reconstruct the original data C(x), since each term corresponds to a symbol error location and magnitude. The error correction procedure is to reconstruct the error polynomial E(x). Three polynomials are used to correct a received polynomial R(x): S(x), a syndrome polynomial; .LAMBDA.(x), an error locator (or error location) polynomial; and .OMEGA.(x) an error magnitude polynomial. The syndromes are computed by evaluating the polynomial R(x) at all roots of G(x). These values are called syndromes and the syndrome polynomial S(x) has these values as coefficients. The syndrome polynomial S(x) is used to determine the existence of errors. The error locator polynomial .LAMBDA.(x) and the error magnitude polynomial .OMEGA.(x) are computed from S(x) by a key equation solver. The roots of the error locator polynomial .LAMBDA.(x) indicate positions in the data that are erroneous and both the error locator polynomial .LAMBDA.(x) and the error magnitude polynomial .OMEGA.(x) are used to determine the true values of the erroneous data.
FIG. 1 illustrates a typical RS decoder unit 100 that is used to determine the error locations and error values. The RS decoder unit 100 comprises a syndrome generator 102, a key equation solver 104, and a Chien search unit 108 for determining the error locations and values. The syndrome generator 102 calculates one syndrome for each of the 2t roots of G(x). The key equation solver 104 utilizes the syndromes to determine the coefficients of the error location polynomial .LAMBDA.(x) and the coefficients of the error magnitude polynomial .OMEGA.(x). The Chien search unit 108 utilizes the error location polynomial .LAMBDA.(x) to search for the roots of the error locator polynomial, r.sub.1, . . . ,r.sub.v. The Chien search unit 108 is a root finding technique which involves evaluating the error locator polynomial at all elements in the field GF(2.sup.n). The roots of the error locator polynomial r.sub.1, . . . ,r.sub.v determine the error locations. The error values are then determined using Forney's algorithm 110. The user data is then corrected using the output of the Forney algorithm unit 110 and the received polynomial R(x) which is transmitted by delay unit 106.
The prior art decoder unit 100 entails a three stage approach with each stage utilizing its own circuitry to perform an intended function. In the first stage, the syndromes are calculated utilizing the circuitry of the syndrome generator 102. The second stage entails determining the coefficients of the error locator and error magnitude polynomials which are performed using the circuitry of the key equation solver 104. The third stage 105 entails the determination of the error location and error values which is performed using the Chien search unit 108 and the Forney's algorithm unit 110.
The Chien search technique is advantageous in that it performs an exhaustive search which can accommodate any number of roots. However, for small values of t, a substantial reduction in the size of the circuitry required to determine the error positions can be achieved by utilizing a different technique. The reduction in circuitry has the consequent advantage of reduced cost and time that cannot be achieved using the Chien search technique and the three stage approach used to implement it.